package com.lft.sort11.bitmap_sort;

import java.util.Arrays;

/**
 * 位图排序
 */
public class BitMapSort {
	public static void main(String[] args) {
		int[] a = {2, 6, 9, 3, 5, 1, -9, 7, -3, -1, -6, 8, 0};
		System.out.println(Arrays.toString(bitMapSort(a)));
	}
	
	public static int[] bitMapSort(int[] a) {
		// 获取原始数组中的最大值最小值。
		int[] maxMinValue = getMaxMinNumbit(a);
		// 通过最大最小值，计算出位图的长度。
		int bitMapLength = (maxMinValue[0] - maxMinValue[1] + 1) / 64 + 1;
		// 创建位图数组。
		long[] bitMap = new long[bitMapLength];
		//
		for (int i = 0; i < a.length; i++) {
			bitMap[(a[i] - maxMinValue[1]) / 64] |= 1L << ((a[i] - maxMinValue[1]) % 64);
		}
		int k = 0;
		int[] temp = new int[a.length];
		
		for (int i = 0; i < bitMapLength; i++) {
			for (int j = 0; j < 64; j++) {
				if ((bitMap[i] & (1L << j)) != 0) {
					temp[k++] = i * 64 + j + maxMinValue[1];
				}
			}
		}
		
		if (k < temp.length) {
			return Arrays.copyOfRange(temp, 0, k);
		}
		
		return temp;
	}
	
	/**
	 * 返回数组中的最大值和最小值。
	 * @param a 原始数组
	 * @return 返回一个集合，里面是最大值和最小值。
	 */
	private static int[] getMaxMinNumbit(int[] a) {
		int max = a[0];
		int min = a[0];
		for (int i = 0; i < a.length; i++) {
			if (a[i] > max) {
				max = a[i];
			} else if (a[i] < min) {
				min = a[i];
			}
		}
		return new int[]{max, min};
	}
	
}
